// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-26 20:06
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class MaxSumSubmatrix {
    /**
     * 矩形区域不超过k的最大数值和
     */
    public int maxSumSubmatrixT(int[][] matrix, int k) {
        int n = matrix.length, m = matrix[0].length, min = Integer.MAX_VALUE, res = -1;
        /*-----构造二维前缀和数组-----*/
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        /*-----朴素遍历-----*/
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        int tmp = sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1];
                        if (tmp <= k) {
                            if (Math.abs(k - tmp) < min) {
                                min = Math.abs(k - tmp);
                                res = tmp;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }


    /**
     * 优化遍历 + Hash 查找
     *
     * @param matrix
     * @param k
     * @return
     */
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int n = matrix.length, m = matrix[0].length, min = Integer.MAX_VALUE, res = Integer.MIN_VALUE;
        /*-----构造二维前缀和数组-----*/
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        /*-----优化枚举（二分查找）-----*/

        for (int top = 1; top <= n; top++) {
            for (int bot = top; bot <= n; bot++) {
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                for (int r = 1; r <= m; r++) {
                    int right = sum[bot][r] - sum[top][r];
                    Integer left = set.ceiling(right - k);
                    if (left != null) {
                        int cur = right - left;
                        res = Math.max(res, cur);
                    }
                    // 遍历过后的右边界可以作为其他子矩阵的左边界
                    set.add(right);
                }
            }
        }
        return res;
    }
}
